{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import log\n",
    "from sklearn import datasets\n",
    "import numpy as np\n",
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "def entropy(y):\n",
    "    \"\"\"信息熵\"\"\"\n",
    "    counter = Counter(y)\n",
    "    res = 0\n",
    "    for num in counter.values():\n",
    "        p = num / len(y)\n",
    "        res += -p * log(p)\n",
    "    return res\n",
    "def split(X,y,d,v):\n",
    "    index_l = X[:,d] <= v\n",
    "    index_r = X[:,d] > v\n",
    "    return X[index_l],X[index_r],y[index_l],y[index_r]\n",
    "def try_split(X,y):\n",
    "    best_d,best_v,best_e = -1,-1,float('inf')\n",
    "    \"\"\"遍历每两个列\"\"\"\n",
    "    for d in range(X.shape[1]):\n",
    "        index = np.argsort(X[:,d])\n",
    "        \"\"\"遍历每行\"\"\"\n",
    "        for l in range(1,len(X)):\n",
    "            if(X[index[l-1],d] != X[index[l],d]):\n",
    "                ave = (X[index[l-1],d] + X[index[l],d])/2\n",
    "                X_l,X_r,y_l,y_r=split(X,y,d,ave)\n",
    "                e  = entropy(y_l) + entropy(y_r)\n",
    "                if(e < best_e):\n",
    "                    best_d,best_v,best_e = d,ave,e\n",
    "    return best_d,best_v,best_e"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [],
   "source": [
    "irs=datasets.load_iris()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [],
   "source": [
    "X=irs.data\n",
    "y=irs.target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [],
   "source": [
    "d,v,e=try_split(X,y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_l,X_r,y_l,y_r=split(X,y,d,ave)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.45"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.6931471805599453"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
